package com.practice.algorithm;

/**
 * 基础的KMP算法
 *KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的高效算法，
 * 其核心思想是利用已经匹配过的部分信息，避免在匹配过程中进行不必要的回溯。具体步骤如下：
 * 构建部分匹配表（Partial Match Table, PMT）：
 * 对于模式串 pattern，计算每个位置之前的子串的最长公共前后缀长度。这个表通常被称为 next 数组。
 * 字符串匹配：
 * 在主串 text 中查找模式串 pattern，使用 next 数组来避免在匹配失败时将模式串的指针完全回溯到开头。
 * @author 不鄢
 */
public class KMPTest {
    /**
     * 生成next数组,即计算最长前后缀长度
     * 最长前后缀长度：前缀和后缀的最长公共部分的长度
     * @param pattern 模式串
     * @return next数组
     */
    public static int[] kmpNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        int len = 0;
        int i = 1;
        next[0] = 0;
        while(i<m){
            if(pattern.charAt(i) == pattern.charAt(len)){
                len++;
                next[i] = len;
                i++;
            }else{
                if(len != 0){
                    len = next[len-1];
                }else{
                    next[i] = 0;
                    i++;
                }
            }
        }
        return next;
    }

    /**
     * kmp搜索
     * @param text 主串
     * @param pattern 模式串
     * @return 匹配的起始位置，如果未找到则返回-1
     */
    public static int kmpSearch(String text,String pattern,int[] next){
        int n = text.length();
        int m = pattern.length();
        int i = 0;
        int j = 0;
        int count = 0;
        while(i<n){
            if(pattern.charAt(j) == text.charAt(i)){
                i++;
                j++;
                count++;
            }

            if(j == m){
                System.out.println("count="+count);
                return i-j;
            }else if( i < n && pattern.charAt(j) != text.charAt(i)){
                if(j != 0){
                    j = next[j-1];
                }else{
                    i++;
                }
                count++;
            }
        }
        System.out.println("count="+count);
        return -1;
    }

    public static void main(String[] args) {
        String str1 = "abaabaabcabaabc";
        String str2 = "abaabc";
        int[] next = kmpNext(str2);
        int index = kmpSearch(str1, str2, next);
        for(int i=0;i<str2.length();i++){
            System.out.print(str2.charAt(i));
        }
        System.out.println();
        for(int i=0;i<next.length;i++){
            System.out.print(next[i]);
        }
        System.out.println();
        System.out.println("index=" + index);
        System.out.println(str1.charAt(index));
    }
}
